/*
 * matrix_graph.c
 *
 *  Created on: 2020��1��9��
 *      Author: Administrator
 */


#include <stdio.h>
#include <stdlib.h>
#include "../../include/queue/linked_queue.h"
#include "../../include/graph/matrix_graph.h"
#include "../../include/stack/seq_stack.h"
#include "../../include/common.h"

AdjMatrix init_graph(int vertex_number) {

	AdjMatrix graph = (AdjMatrix)malloc(sizeof(GNode));
	graph->vertex_number = vertex_number;
	graph->edge_number = 0;
	graph->is_directed = false;

	for (int i = 0; i < graph->vertex_number; i++) {
		for (int j = 0; j < graph->vertex_number; j++) {
			if (graph->is_directed == false)
				graph->graph[i][j] = 0;       // 无向图
			else
				graph->graph[i][j] = INFINITY; // 有向图
		}
	}

	return graph;
}

void build_graph(AdjMatrix graph, Edge edges[], int edges_number) {

	if (graph == NULL) return;

	for (int i = 0; i < edges_number; ++i) {
		if (insert_edge(graph, edges[i]) == false) {
			printf("insert fail: %d->%d\n", edges[i]->v1, edges[i]->v2);
			return;
		}
	}
	printf("insert succeed!\n");
}

Edge* build_edges(int edges_number, int input[][3]) {

	Edge* edges = (Edge*)malloc(sizeof(Edge) * edges_number);

	for (int i = 0; i < edges_number; ++i) {
		Edge edge = (Edge)malloc(sizeof(ENode));
		edge->v1 = input[i][0];
		edge->v2 = input[i][1];
		edge->weight = input[i][2];
		edges[i] = edge;
	}
	return edges;
}

bool insert_edge(AdjMatrix graph, Edge edge) {

	if (graph == NULL || edge == NULL) return false;
	// 如果为无向图
	if (graph->is_directed == false) {
		graph->graph[edge->v1][edge->v2] = 1;
		graph->graph[edge->v2][edge->v1] = 1;
	} else {
		graph->graph[edge->v1][edge->v2] = edge->weight;
	}
	graph->edge_number += 1;
	return true;
}

void visit(Vertex v) {
	if (is_not_visited(v)) {
		printf("%d ", v);
		visited[v] = true;
	}
}

bool is_not_visited(Vertex v) {
	if (visited[v] == false) return true;
	return false;
}

bool is_visited(Vertex v) {
	if (visited[v] == true) return true;
	return false;
}

bool has_edge(AdjMatrix graph, Vertex v1, Vertex v2) {
	if (graph == NULL) {
		return false;
	} else {
		if ( graph->graph[v1][v2] != 0) {
			return true;
		} else {
			return false;
		}
	}
}

void clear_visited(int vertex_number) {

	for (int i = 0; i < vertex_number; ++i) {
		visited[i] = false;
	}
}

void dfs(AdjMatrix graph, Vertex start) {

	if (graph == NULL) return;

	if (is_not_visited(start)) {
		visit(start);
	}

	for (int i = 0; i < graph->vertex_number; ++i) {
		if (has_edge(graph, start, i) && is_not_visited(i)) {
			dfs(graph, i);
		}
	}
}

void unr_dfs(AdjMatrix graph, Vertex start) {

	// 使用栈存储没有访问过的结点
	SeqStack* stack = (SeqStack* )malloc(sizeof(SeqStack));
	init_seqstack(stack);

	Vertex temp;
	visit(start);
	push_seqstack(stack, (ElemType)start);

	while (!is_empty_seqstack(stack)) {

		temp = first_adj_vertex(graph, start);    // 前进，找到start的第一个邻接点

		while (temp != -1) {
			if (!is_visited(temp)) {
				visit(temp);
				push_seqstack(stack, (ElemType)temp); // 保存回溯点
				break;
			} else {
				temp = next_adj_vertex(graph, start, temp);  // 探索其他邻接点
			}
		}

		if (temp == -1) {         // 如果无法再往前走了，则回溯
			pop_seqstack(stack);  // 返回上一回溯点
			start = peek_seqstack(stack);
		} else {
			start = temp;         // 更新
		}
	}
}

Vertex first_adj_vertex(AdjMatrix graph, Vertex start) {

	if (graph == NULL) return NOT_FOUND;

	for (int i = 0; i < graph->vertex_number; ++i) {
		if (graph->graph[start][i] == 1)
			return i;
	}
	return NOT_FOUND;
}

Vertex last_adj_vertex(AdjMatrix graph, Vertex start) {

	if (graph == NULL) return NOT_FOUND;

	for (int i = graph->vertex_number - 1; i >= 0; --i) {
		if (graph->graph[start][i] == 1)
			return i;
	}
	return NOT_FOUND;
}

Vertex next_adj_vertex(AdjMatrix graph, Vertex start, Vertex next) {

	if (graph == NULL) return NOT_FOUND;

	for (int i = next + 1; i < graph->vertex_number; ++i) {
		if (graph->graph[start][i] == 1)
			return i;
	}
	return NOT_FOUND;
}

Vertex pre_adj_vertex(AdjMatrix graph, Vertex start, Vertex next) {

	if (graph == NULL) return NOT_FOUND;

	for (int i = next - 1; i >= 0 ; --i) {
		if (graph->graph[start][i] == 1)
			return i;
	}
	return NOT_FOUND;
}

void bfs(AdjMatrix graph, Vertex start) {

	if (graph == NULL) return;

	LinkedQueue* queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	init_queue(queue);

	enqueue(queue, (int)start);

	while (!is_queue_empty(queue)) {

		Vertex temp = (Vertex)dequeue(queue); // 出队

		if (is_not_visited(temp)) {
			visit(temp);
		}

		for (int i = 0; i < graph->vertex_number; ++i) {
			if (has_edge(graph, temp, i) && is_not_visited(i)) {
				enqueue(queue, i);
			}
		}
	}
}

void print_matrix_graph(AdjMatrix graph) {

	if (graph == NULL) {
		return;
	} else {
		for (int i = 0; i < graph->vertex_number; ++i) {
			for (int j = 0; j < graph->vertex_number; ++j) {
				printf("%d ", graph->graph[i][j]);
			}
			printf("\n");
		}
		printf("\n");
	}
}
